package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 2020-11-25 14:01
 *
 * https://leetcode-cn.com/problems/maximum-gap/
 */
public class _164_最大间距_01 {

    public int maximumGap(int[] nums) {

        if (nums == null || nums.length <= 1) {

            return 0;
        }

        int min = nums[0], max = nums[1];

        for (int num : nums) {

            if (num < min) {
                min = num;
            }

            if (num > max) {

                max = num;
            }
        }

        if (min == max) {

            return 0;
        }


        int bucktNum = nums.length - 1;

        int avgGap = (int) Math.ceil((max - min) * 1.0 / bucktNum);
        if (avgGap == 0) {

            avgGap = 1;

        }

        int[] everyBucktMin = new int[bucktNum];
        int[] everyBucktMax = new int[bucktNum];
        int[] buckts = new int[bucktNum];

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] == max) {
                continue;
            }

            int index = (nums[i] - min) / avgGap;

            // 第一次放入到对应的桶中
            if (buckts[index] == 0) {

                everyBucktMin[index] = nums[i];
                everyBucktMax[index] = nums[i];

                buckts[index]++;
            }else {

                if (nums[i] < everyBucktMin[index]) {

                    everyBucktMin[index] = nums[i];
                }

                if (nums[i] > everyBucktMax[index]) {

                    everyBucktMax[index] = nums[i];
                }
            }
        }

        int maxGap = avgGap;
        int index = 0;

        while (index < buckts.length) {

            if (buckts[index] == 0) {

                index++;
            }else {

                int j = index + 1;

                while (j < buckts.length && buckts[j] == 0) {

                    j++;
                }

                if (j == buckts.length) {

                    break;
                }

                int gap = everyBucktMin[j] - everyBucktMax[index];

                if (gap > maxGap) {

                    maxGap = gap;
                }

                index = j;
            }
        }

        if (index < buckts.length && maxGap < max - everyBucktMax[index]) {

            maxGap = max - everyBucktMax[index];
        }

        return maxGap;
    }
}
